SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>FP (programming language)</title>

</head>

FP (programming language)

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox vevent"><tbody><tr><th colspan="2" class="infobox-above" style="background-color:#e0e0e0;">FP</th></tr><tr><th scope="row" class="infobox-label"><a href="Programming_paradigm" title="Programming paradigm">Paradigm</a></th><td class="infobox-data"><a href="Function-level_programming" title="Function-level programming">Function-level</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Software_design" title="Software design">Designed by</a></th><td class="infobox-data"><a href="John_Backus" title="John Backus">John Backus</a></td></tr><tr><th scope="row" class="infobox-label">First appeared</th><td class="infobox-data">1977</td></tr><tr><th colspan="2" class="infobox-header" style="background-color: #EEEEEE;"><a href="Programming_language#Dialects,_flavors_and_implementations" title="Programming language">Dialects</a></th></tr><tr><td colspan="2" class="infobox-full-data">FP84</td></tr><tr><th colspan="2" class="infobox-header" style="background-color: #EEEEEE;">Influenced by</th></tr><tr><td colspan="2" class="infobox-full-data"><a href="APL_(programming_language)" title="APL (programming language)">APL</a><a href="#cite_note-Hudak_1989-1">[1]</a></td></tr><tr><th colspan="2" class="infobox-header" style="background-color: #EEEEEE;">Influenced</th></tr><tr><td colspan="2" class="infobox-full-data"><a href="FL_(programming_language)" title="FL (programming language)">FL</a>, <a href="Haskell_(programming_language)" class="mw-redirect" title="Haskell (programming language)">Haskell</a>, <a href="Joy_(programming_language)" title="Joy (programming language)">Joy</a></td></tr></tbody></table>

FP (short for functional programming)<a href="#cite_note-Backus_1977-2">[2]</a> is a <a href="Programming_language" title="Programming language">programming language</a> created by <a href="John_Backus" title="John Backus">John Backus</a> to support the <a href="Function-level_programming" title="Function-level programming">function-level programming</a><a href="#cite_note-Backus_1977-2">[2]</a> paradigm. It allows building programs from a set of generally useful primitives and avoiding named variables (a style also called <a href="Tacit_programming" title="Tacit programming">tacit programming</a> or "point free"). It was heavily influenced by <a href="APL_(programming_language)" title="APL (programming language)">APL</a> developed by <a href="Kenneth_E._Iverson" title="Kenneth E. Iverson">Kenneth E. Iverson</a> in the early 1960s.<a href="#cite_note-acm-3">[3]</a>

The FP language was introduced in Backus's 1977 <a href="Turing_Award" title="Turing Award">Turing Award</a> paper, "Can Programming Be Liberated from the von Neumann Style?", subtitled "a functional style and its algebra of programs." The paper sparked interest in <a href="Functional_programming" title="Functional programming">functional programming</a> research,<a href="#cite_note-4">[4]</a> eventually leading to modern functional languages, which are largely founded on the <a href="Lambda_calculus" title="Lambda calculus">lambda calculus</a> paradigm, and not the function-level paradigm Backus had hoped. In his Turing award paper, Backus described how the FP style is different:

/* start https://en.wikipedia.org/ */

.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}

/* end https://en.wikipedia.org/ */

</style><blockquote class="templatequote">An FP system is based on the use of a fixed set of combining forms called functional forms. These, plus simple definitions, are the only means of building new functions from existing ones; they use no variables or substitutions rules, and they become the operations of an associated algebra of programs. All the functions of an FP system are of one type: they map objects onto objects and always take a single argument.<a href="#cite_note-Backus_1977-2">[2]</a></blockquote>

FP itself never found much use outside of academia.<a href="#cite_note-p21-5">[5]</a> In the 1980s Backus created a successor language, <a href="FL_(programming_language)" title="FL (programming language)">FL</a> as an internal project at <a href="IBM_Research" title="IBM Research">IBM Research</a>.

<div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2></div>

The values that FP programs map into one another comprise a <a href="Set_(abstract_data_type)" title="Set (abstract data type)">set</a> which is <a href="Closure_(mathematics)" title="Closure (mathematics)">closed</a> under sequence formation:

<pre>if x1,...,xn are values, then the sequence 〈x1,...,xn〉 is also a value

</pre>

These values can be built from any set of atoms: booleans, integers, reals, characters, etc.:

<pre>boolean  : {T, F}

integer  : {0,1,2,...,∞}

character : {'a','b','c',...}

symbol  : {x,y,...}

</pre>

⊥ is the undefined value, or bottom. Sequences are bottom-preserving:

<pre>〈x1,...,⊥,...,xn〉 = ⊥

</pre>

FP programs are functions f that each map a single value x into another:

<pre>f:x represents the value that results from applying the function f

to the value x

</pre>

Functions are either primitive (i.e., provided with the FP environment) or are built from the primitives by program-forming operations (also called functionals).

An example of primitive function is constant, which transforms a value x into the constant-valued function x̄. Functions are <a href="Strict_function" title="Strict function">strict</a>:

<pre>f:⊥ = ⊥

</pre>

Another example of a primitive function is the selector function family, denoted by 1,2,... where:

<pre>i:〈x1,...,xn〉 = xi if 1 ≤ i ≤ n

= ⊥ otherwise

</pre>

<div class="mw-heading mw-heading2"><h2 id="Functionals">Functionals</h2></div>

In contrast to primitive functions, functionals operate on other functions. For example, some functions have a unit value, such as 0 for addition and 1 for multiplication. The functional unit produces such a value when applied to a function f that has one:

<pre>unit + = 0

unit × = 1

unit foo = ⊥

</pre>

These are the core functionals of FP:

<pre>composition f∘g where f∘g:x = f:(g:x)

</pre>

<pre>construction [f1,...,fn] where [f1,...,fn]:x = 〈f1:x,...,fn:x〉

</pre>

<pre>condition (h ⇒ f;g) where (h ⇒ f;g):x = f:x if h:x = T

= g:x if h:x = F

= ⊥ otherwise

</pre>

<pre>apply-to-all αf where αf:〈x1,...,xn〉 = 〈f:x1,...,f:xn〉

</pre>

<pre>insert-right /f where /f:〈x〉 = x

and /f:〈x1,x2,...,xn〉 = f:〈x1,/f:〈x2,...,xn〉〉

and /f:〈〉 = unit f

</pre>

<pre>insert-left \f where \f:〈x〉 = x

and \f:〈x1,x2,...,xn〉 = f:〈\f:〈x1,...,xn-1〉,xn〉

and \f:〈〉 = unit f

</pre>

<div class="mw-heading mw-heading2"><h2 id="Equational_functions">Equational functions</h2></div>

In addition to being constructed from primitives by functionals, a function may be defined recursively by an equation, the simplest kind being:

<pre>f ≡ Ef

</pre>

where Ef is an <a href="Expression_(computer_science)" title="Expression (computer science)">expression</a> built from primitives, other defined functions, and the function symbol f itself, using functionals.

FP84 is an extension of FP to include <a href="Infinite_sequence" class="mw-redirect" title="Infinite sequence">infinite sequences</a>, programmer-defined <a href="Combining_form" class="mw-redirect" title="Combining form">combining forms</a> (analogous to those that Backus himself added to <a href="FL_programming_language" class="mw-redirect" title="FL programming language">FL</a>, his successor to FP), and <a href="Lazy_evaluation" title="Lazy evaluation">lazy evaluation</a>. Unlike FFP, another one of Backus' own variations on FP, FP84 makes a clear distinction between objects and functions: i.e., the latter are no longer represented by sequences of the former. FP84's extensions are accomplished by removing the FP restriction that sequence construction be applied only to non-⊥ objects: in FP84 the entire universe of expressions (including those whose meaning is ⊥) is <a href="Closed_under" class="mw-redirect" title="Closed under">closed under</a> sequence construction.

FP84's semantics are embodied in an underlying algebra of programs, a set of <a href="Function-level_programming" title="Function-level programming">function-level</a> equalities that may be used to manipulate and reason about programs.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-Hudak_1989-1"><a href="#cite_ref-Hudak_1989_1-0">^</a> <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/72551.72554">The Conception, Evolution, and Application of Functional Programming Languages</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160311204021/http://haskell.cs.yale.edu/wp-content/uploads/2011/01/cs.pdf">Archived</a> 2016-03-11 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> Paul Hudak, 1989

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBackus1978" class="citation journal cs1">Backus, J. (1978). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F359576.359579">"Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs"</a>. Communications of the ACM. 21 (8): 613. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F359576.359579">10.1145/359576.359579</a>.</cite>

</li>

<li id="cite_note-acm-3"><a href="#cite_ref-acm_3-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://signallake.com/innovation/JBackus032007.pdf">"Association for Computing Machinery A. M. Turing Award"</a> (PDF).</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFYang2017" class="citation web cs1">Yang, Jean (2017). <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~popl-interviews/peytonjones.html">"Interview with Simon Peyton-Jones"</a>. People of Programming Languages.</cite>

</li>

<li id="cite_note-p21-5"><a href="#cite_ref-p21_5-0">^</a> <cite id="CITEREFHague2007" class="citation web cs1">Hague, James (December 28, 2007). <a rel="nofollow" class="external text" href="http://prog21.dadgum.com/14.html">"Functional Programming Archaeology"</a>. Programming in the Twenty-First Century.</cite>

</li>

</ol></div></div>

<ul><li>Sacrificing simplicity for convenience: Where do you draw the line?, John H. Williams and Edward L. Wimmers, IBM Almaden Research Center, Proceedings of the Fifteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, San Diego, CA, January 1988.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://pointfree-interpreter.github.io/">FP-Interpreter</a> written in Delphi/Lazarus</li>

<li><a rel="nofollow" class="external text" href="http://dirkgerrits.com/publications/john-backus.pdf#section.9">Dirk Gerrits: Turing Award lecture (1977-1978) ff</a>, in John W. Backus (Publications)</li>

<li>FP84 vs FL: <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/pdf/10.1145/73560.73575">Sacrificing simplicity for convenience: Where do you draw the line?</a> J.H. William and E.L. Wimmers, 1988 (Pages 169–179)</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-04-08" href="https://en.wikipedia.org/wiki/?title=FP_(programming_language)&oldid=1217859699">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>